#pragma once
#include <string>
#include <iostream>
using namespace std;


struct node
{
	node *next;
	string value;

	node()
	{
		next = nullptr;
	}

	node(const string &t)
	{
		value = t;
		next = nullptr;
	}
};

class circular_list
{
private:
	class iterator
	{
	public:
		typedef iterator self_type;
		typedef node  value_type;
		typedef node& reference;
		typedef node* pointer;
		typedef std::forward_iterator_tag iterator_category;
		typedef int difference_type;

		iterator(pointer ptr) : ptr_(ptr) { } 
		self_type operator++()
		{
			self_type i = *this;
			ptr_ = ptr_->next;
			return i;
		}
		self_type operator++(int junk) { ptr_ = ptr_->next; return *this; }
		reference operator*() { return *ptr_; }
		pointer operator->() { return ptr_; }
		bool operator==(const self_type& rhs) { return ptr_ == rhs.ptr_; }
		bool operator!=(const self_type& rhs) { return ptr_ != rhs.ptr_; }

	private:
		pointer ptr_;
	};
	node sentinel;
public:

	circular_list()
	{
		sentinel.next = &sentinel;
	}

	circular_list(const circular_list &obj)
	{
		this->sentinel.next = &this->sentinel;
		node *temp = obj.sentinel.next;
		while (temp != &obj.sentinel)
		{
			this->addLast(temp->value);
			temp = temp->next;
		}
	}

	circular_list &operator=(const circular_list &obj)
	{
		this->clear();
		node *temp = obj.sentinel.next;
		while (temp != &obj.sentinel)
		{
			this->addLast(temp->value);
			temp = temp->next;
		}
		return *this;
	}

	void clear()
	{
		if (sentinel.next == &sentinel)
		{
			return;
		}
		else
		{
			node *c = sentinel.next;
			while (c != &sentinel)
			{
				node *tmp = c;
				c = c->next;
				delete tmp;
			}

			sentinel.next = &sentinel;
		}
	}

	void print()
	{
		node *temp = sentinel.next;
		while (temp != &sentinel)
		{
			cout << temp->value << endl;
			temp = temp->next;
		}
	}

	node GetSentinel() { return sentinel; }
	bool is_empty() { return sentinel.next == &sentinel; }

	string& front()
	{
		if (sentinel.next != nullptr)
		{
			return sentinel.next->value;
		}

		else
		{
			throw exception("circular_list::front, empty list");
		}
	}

	string& back()
	{
		if (sentinel.next != nullptr)
		{
			node *temp = sentinel.next;
			while (temp != &sentinel)
			{
				if (temp->next == &sentinel)
				{
					return temp->value;
				}
				temp = temp->next;
			}
		}
		else
		{
			throw exception("ciruclar_list::back, empty list");
		}
	}

	void addLast(const string &value)
	{
		if (sentinel.next == &sentinel)
		{
			node *n = new node(value);
			sentinel.next = nullptr;
			sentinel.next = n;
			n->next = &sentinel;
		}

		else
		{
			node *temp = sentinel.next;
			while (temp->value != this->back())
			{
				temp = temp->next;
			}
			node *n = new node(value);
			temp->next = n;
			n->next = &sentinel;
		}
	}

	void add(const string &value)
	{
		if (sentinel.next == &sentinel)
		{
			node *n = new node(value);
			sentinel.next = nullptr;
			sentinel.next = n;
			n->next = &sentinel;
		}

		else
		{
			node *n = new node(value);
			n->next = sentinel.next;
			sentinel.next = n;
		
		}
	}

	void remove(const string &value)
	{
		node * b = nullptr;
		node *temp = sentinel.next;
		while (temp->value != value)
		{
			temp = temp->next;
		}

		if (temp->value == this->front())
		{
			sentinel.next = sentinel.next->next;
			delete temp;
		}

		else if (temp->value == this->back())
		{
			b = this->NodeBefore(temp->value);
			b->next = &sentinel;
			delete temp;
		}

		else
		{
			b = this->NodeBefore(temp->value);
			b->next = temp->next;
			delete temp;
		}

	}

	node* NodeBefore(const string &value)
	{
		node *temp = sentinel.next;

		while (temp != &sentinel)
		{
			if (temp->next->value == value)
			{
				return temp;
			}
			else if (temp->value == value)
			{
				return temp;
			}
			temp = temp->next;
		}
		return nullptr;
	}

	bool oneRemaining()
	{
		if (sentinel.next->next == &sentinel)
		{
			return true;
		}

		return false;
	}

	iterator begin() { return iterator(sentinel.next); }
	iterator end() { return iterator(&sentinel); }

	~circular_list()
	{
		this->clear();
	}
};

